#include <vector>

using namespace std;

// 岛屿数量
// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
// 此外，你可以假设该网格的四条边均被水包围
// 测试链接 : https://leetcode.cn/problems/number-of-islands/

// 洪水填充的做法
// board : n * m
// O(n*m)最优解！
class Solution 
{
private:
    int m, n;
    int move[5] = {-1, 0, 1, 0, -1};

    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') return;

        grid[i][j] = '2'; // 标记该位置已经访问过了
        dfs(grid, i - 1, j); // 上
        dfs(grid, i + 1, j); // 下
        dfs(grid, i, j - 1); // 左
        dfs(grid, i, j + 1); // 右
    }

public:
    int numIslands(vector<vector<char>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        int ret = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == '1')
                {
                    ++ret;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }
};

// 另一种 dfs 的解法
class Solution 
{
private:
    int m, n;
    int move[5] = {-1, 0, 1, 0, -1};

    void dfs(vector<vector<char>>& grid, int i, int j)
    {
        grid[i][j] = '2'; // 标记该位置已经访问过了
        for(int k = 0; k < 4; ++k)
        {
            int x = i + move[k], y = j + move[k + 1];
            if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') 
                dfs(grid, x, y);
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        int ret = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == '1')
                {
                    ++ret;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }
};

// bfs 的解法
class Solution 
{
private:
    int m, n;
    int move[5] = {-1, 0, 1, 0, -1};
    
    void bfs(vector<vector<char>>& grid, int i, int j)
    {
        queue<int> q;
        q.emplace(i * n + j);
        grid[i][j] = '2';

        while(!q.empty())
        {
            int pos = q.front();
            q.pop();
            for(int k = 0; k < 4; ++k)
            {
                int x = pos / n + move[k];
                int y = pos % n + move[k + 1];
                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1')
                {
                    grid[x][y] = '2';
                    q.push(x * n + y);
                }
            }
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) 
    {
        m = grid.size(), n = grid[0].size();
        int ret = 0;
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j] == '1')
                {
                    ++ret;
                    bfs(grid, i, j);
                }
            }
        }

        return ret;
    }
};